package com.ujs.code.removeElement;

import java.util.Arrays;

/**
 * @author zhangshihao
 * @create 2023-09-10 22:33
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {3, 2, 2, 3};
        int val = 3;
        // int baoli = solution.baoli(nums, val);
        // System.out.println(baoli);

        int i = solution.doublePointer2(nums, val);
        System.out.println(i);
    }


    public int baoli(int[] nums, int val) {
        int size = nums.length;
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) { // 发现需要删除的数组，全体数组向前移动一位
                for (int j = i; j < size - 1; j++) {
                    nums[j] = nums[j + 1];
                }
                i--; // 因为后面的元素向前移动了一位，所以i也应该向前移动，找到元素
                size--;
            }
        }
        System.out.println(Arrays.toString(nums));
        return size;
    }


    /**
     * 快慢指针法
     *
     * @param nums
     * @param val
     * @return
     */
    public int doublePointer(int[] nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }

    /**
     * 相向双指针法，基于元素顺序可以改变的题目描述改变了元素相对位置，确保了移动最少元素
     * 找到左边
     *
     * @param nums
     * @param val
     * @return
     */
    public int doublePointer2(int[] nums, int val) {
        int leftIndex = 0;
        int rightIndex = nums.length - 1;
        while (leftIndex <= rightIndex) {
            while (leftIndex <= rightIndex && nums[leftIndex] != val) { // 一直找到左侧的和val相等的点
                ++leftIndex;
            }
            while (leftIndex <= rightIndex && nums[rightIndex] != val) { // 一直找到右侧的和val相等的点
                --rightIndex;
            }
            if (leftIndex < rightIndex) { // 将右边不等于val的元素覆盖左边等于val的元素
                nums[leftIndex++] = nums[rightIndex--];
            }
        }
        return leftIndex; // leftIndex一定指向了最终数组末尾的下一个元素
    }
}
